package B刷题.暴力递归.A回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wei.zhao
 * @description: 51.N皇后
 * @date 2022年12月03日 11:25
 */
public class Code08_SolveNQueens {

    String s = "";

    List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        if (n < 1) {
            return result;
        }
        for (int i = 0; i < n; i++) {
            s += ".";
        }
        process(new int[n], 0);
        return result;
    }

    void process(int[] arr, int row) {
        if (row == arr.length) {
            List<String> list = new ArrayList<>();
            for (int i : arr) {
                list.add(s.substring(0, i) + "Q" + s.substring(i + 1));
            }
            result.add(list);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (isValid(arr, row, i)) {
                arr[row] = i;
                process(arr, row + 1);
            }
        }
    }

    public boolean isValid(int[] arr, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (arr[i] == col || Math.abs(row - i) ==Math.abs(col - arr[i])) {
                return false;
            }
        }
        return true;
    }

}
